package g

import (
	"math"
)

/*
 * @lc app=leetcode.cn id=29 lang=golang
 *
 * [29] 两数相除

给定两个整数，被除数 dividend 和除数 divisor。
将两数相除dividend/divisor，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，
例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

被除数和除数均为 32 位有符号整数。除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31,  2^31 − 1]。
本题中，如果除法结果溢出，则返回 2^31 − 1。
*/

// @lc code=start
func divide(dividend int, divisor int) int {
	// return divide(dividend, divisor) // Time Limit Exceeded
	return divide2(dividend, divisor) // Time Limit Exceeded
}

// Time Limit Exceeded
func divide1(dividend int, divisor int) int {
	if dividend == 0 {
		return 0
	}
	if dividend > 0 && divisor > 0 {
		return dividePositive(dividend, divisor)
	} else if dividend > 0 && divisor < 0 {
		divisor = 0 - divisor
		return 0 - dividePositive(dividend, divisor)
	} else if dividend < 0 && divisor > 0 {
		dividend = 0 - dividend
		return 0 - dividePositive(dividend, divisor)
	}
	if dividend == math.MinInt32 && divisor == -1 { //唯一越界情况
		return math.MaxInt32
	}
	if dividend > divisor {
		return 0
	} else if dividend == divisor {
		return 1
	}
	dividend -= divisor // 避免越界,返回值+1补回,比如 dividend=math.MinInt32,divisor=-2
	dividend = 0 - dividend
	divisor = 0 - divisor
	return 1 + dividePositive(dividend, divisor)
}

func dividePositive(dividend int, divisor int) int {
	var result int
	for {
		if divisor <= dividend {
			dividend -= divisor
			result++
		} else {
			return result
		}
	}
}

func divide2(dividend int, divisor int) int {
	if dividend == 0 {
		return 0
	}
	if dividend == math.MinInt32 && divisor == -1 { //唯一越界情况
		return math.MaxInt32
	}
	if divisor == math.MinInt32 {
		if dividend == math.MinInt32 {
			return 1
		}
		return 0
	}
	// 剩下情况，全部转为负数进行计算
	if dividend > 0 && divisor > 0 {
		return divideNegative(0-dividend, 0-divisor)
	} else if dividend > 0 && divisor < 0 {
		return 0 - divideNegative(0-dividend, divisor)
	} else if dividend < 0 && divisor > 0 {
		return 0 - divideNegative(dividend, 0-divisor)
	}
	return divideNegative(dividend, divisor)
}

// 负数除法
func divideNegative(dividend int, divisor int) int {
	if dividend > divisor {
		return 0
	}
	var resultAll int
	result := 1
	divisorNew := divisor
	for {
		if divisorNew > dividend-divisorNew { // 指数递增
			divisorNew += divisorNew
			result += result
		} else {
			resultAll += result
			if divisorNew < dividend-divisor { // 结束条件
				break
			}
			result = 1 // 重新指数递增
			dividend -= divisorNew
			divisorNew = divisor
		}
	}
	return resultAll
}

// @lc code=end
